// Copyright 2011 Google Inc. All Rights Reserved.
// Author: jacobsa@google.com (Aaron Jacobs)
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/**
 * Detect whether the graph defined by the supplied adjacency list contains a
 * cycle. If so, return a representative node.
 *
 * @param {!Array.<!flame.internal.GraphEdge>} edges
 *     The set of edges in the graph.
 *
 * @return {?string}
 *     A node involved in a cycle if there is one, or null otherwise.
 */
flame.internal.findCycle = function(edges) {
  // Perform a "colored DFS", as described here:
  //
  //     http://www.cs.berkeley.edu/~kamil/teaching/sp03/041403.pdf
  //
  // All nodes are initially marked white. When a node is encountered, it is
  // marked grey, and when its descendents are completely visited it is marked
  // black.
  //
  // If we encounter a grey node, then it means that we have revisited a node
  // before finishing up with all of its descendents, and thus it is a
  // descendent of itself. Therefore if a grey node is encountered, there is a
  // cycle.
  //
  // If there is a cycle, then a node A must be accessible from itself. So
  // when it is in the process of being searched, it will be visited again. At
  // this time it will be marked grey. Therefore if there is a cycle, then a
  // grey node will be enountered.
  //
  // Thus there is a cycle if and only if a grey node is encountered.

  /** @type {!flame.internal.StringMap} */
  var colors = new flame.internal.StringMap;

  // Initially mark all nodes as white.
  for (var i = 0; i < edges.length; ++i) {
    var fromNode = edges[i].fromNode;
    var toNode = edges[i].toNode;

    if (!(colors.contains(fromNode))) colors.insert(fromNode, 'white');
    if (!(colors.contains(toNode))) colors.insert(toNode, 'white');
  }

  // Visit each node that is still white.
  var nodes = colors.getKeys();
  for (var i = 0; i < nodes.length; ++i) {
    var node = nodes[i];

    if (colors.get(node) == 'white') {
      var result = flame.internal.findCycle.visit_(node, edges, colors);
      if (result != null) {
        return result;
      }
    }
  }

  return null;
};

/**
 * Implements part of the algorithm described above.
 *
 * @param {string} node
 * @param {!Array.<!flame.internal.GraphEdge>} edges
 * @param {!flame.internal.StringMap} colors
 *
 * @return {?string}
 *     A node involved in a cycle if one is found, or null otherwise.
 */
flame.internal.findCycle.visit_ = function(node, edges, colors) {
  colors.insert(node, 'grey');

  for (var i = 0; i < edges.length; ++i) {
    var edge = edges[i];
    if (edge.fromNode != node) continue;

    if (colors.get(edge.toNode) == 'grey') {
      return edge.toNode;
    }

    if (colors.get(edge.toNode) == 'white') {
      var result = flame.internal.findCycle.visit_(edge.toNode, edges, colors);
      if (result != null) {
        return result;
      }
    }
  }

  colors.insert(node, 'black');
  return null;
};
